/**
 * 将有序数组转化为二叉搜索树
 *
 * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
 *
 * 示例 1：
 * 输入：nums = [-10,-3,0,5,9]
 * 输出：[0,-3,9,-10,null,5]
 * 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
 *
 * 示例 2：
 * 输入：nums = [1,3]
 * 输出：[3,1]
 * 解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
 *
 * 提示：
 * 1 <= nums.length <= 104
 * -104 <= nums[i] <= 104
 * nums 按 严格递增 顺序排列
 */

/**
 * 1. 递归, 首先这是一个升序的数组, 我们要想得到平衡二叉树, 那么中间的节点
 * 一定是 nums 的中间数, 那么我们就可以写一个递归, 用来在一定区间里获得平衡
 * 二叉树
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(log n)
 *
 * 2. 平衡大法, 类似于源码的平衡树, 使用左旋, 右旋 来使树平衡
 * 时间复杂度 : O(n ^ 2)
 * 空间复杂度 : O(n)
 */

public class Main {

    // **************************************************
    // 1. 递归
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }

    public TreeNode dfs(int[] nums, int start, int end) {

        if (start > end) {
            return null;
        }

        int mid = start + (end - start) / 2;

        TreeNode root = new TreeNode(nums[mid]);

        root.left = dfs(nums, start, mid - 1);
        root.right = dfs(nums, mid + 1, end);

        return root;
    }

    public TreeNode root = null;


    // ******************************************************
    // 2. 平衡法
    public TreeNode sortedArrayToBST2(int[] nums) {

        for(int num : nums) {
            root = add(root, num);
        }
        return root;
    }

    public TreeNode add(TreeNode node, int val) {
        if(node == null) {
            node = new TreeNode(val);
            return node;
        }

        // 添加操作
        if(val < node.val) { // val 位于左树
            node.left = add(node.left, val);
        } else if(val > root.val) { // val 位于右树
            node.right = add(node.right, val);
        }
        // nums严格递增不存在相同元素, 不处理 val == node.val 情况

        // 计算平衡因子
        int balanceFactor = getBalanceFactor(node);

        // 维护平衡
        // 当 node 左树倾斜, 并且 node.left 的左树高于右树, 右旋转 node
        if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
            return rightRotate(node);
        }
        // 当 node 右树倾斜, 并且 node.right 的右树高于左树, 左旋转 node
        if(balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
            return leftRotate(node);
        }

        // 当 node 左树倾斜, 并且 node.left 的左树低于右树, 先左旋转 node.left 再右旋转 node
        if(balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // 当 node 右树倾斜, 并且 node.right 的右树低于左树, 先右旋转 node.right 再左旋转 node
        if(balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        // 平衡未破坏
        return node;
    }

    public int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }

    public int getBalanceFactor(TreeNode root) {
        return getHeight(root.left) - getHeight(root.right);
    }

    public TreeNode rightRotate(TreeNode root) {
        TreeNode leftNode = root.left;
        root.left = leftNode.right;
        leftNode.right = root;
        return leftNode;
    }

    public TreeNode leftRotate(TreeNode root) {
        TreeNode rightNode = root.right;
        root.right = rightNode.left;
        rightNode.left = root;
        return rightNode;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}